#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

class Solution {
public:
    void showAll(const std::vector<std::vector<int>> &raw){
        for(int i=0;i<=int(raw.size())-1;i++){
            for(int j=0;j<=int(raw[i].size())-1;j++){
                std::cout<<raw[i][j]<<' ';
            }std::cout<<std::endl;
        }
    }

    int sum(const std::vector<int> &a){
        int sum=0;
        for(int i=0;i<=int(a.size())-1;i++){
            sum+=a[i];
        }
        return sum;
    }
    
    int minItem(const std::vector<int> &a){
        int record=a[0];
        for(int i=1;i<=int(a.size())-1;i++){
            if(record>a[i]){
                record=a[i];
            }
        }
        return record;
    }

    int maxItem(const std::vector<int> &a){
        int record=a[0];
        for(int i=1;i<=int(a.size())-1;i++){
            if(record<a[i]){
                record=a[i];
            }
        }
        return record;
    }

    int subsetsCount(const std::vector<int> &raw, const int target){
        // 处理特殊情况
        if(raw.empty()){
            return (target==0);
        } // raw非空
        if(raw.size()==1){
            return (target==0)+(raw[0]==target);
        } // raw个数>=2
        if(target!=0 && target<minItem(raw)){
            return 0;
        }
        if(target>sum(raw)){
            return 0;
        }

        
        std::vector<std::vector<int>> board(raw.size(),
            std::vector<int>(target+1,0));
        const int n=raw.size(); // n>=2
        for(int i=0;i<=n-1;i++){
            board[i][0]=1;
        }
        board[0][raw[0]]+=1;

        
        for(int i=1;i<=n-1;i++){
            for(int j=0;j<=target;j++){
                board[i][j]=board[i-1][j];
                if(j>=raw[i]){
                    board[i][j]+=board[i-1][j-raw[i]];
                }
            }
        }

        // showAll(board);

        return board[n-1][target];
    }

    int findTargetSumWays(const std::vector<int>& nums, int target) {
        const int total=sum(nums);
        const int level=(total+target)/2;
        if((total+target)%2!=0){
            return 0;
        }
        return subsetsCount(nums,level);
    }
};

int main(){
    Solution test{};
    const std::vector<int> raw={1};
    std::cout<<test.findTargetSumWays(raw,1);
    return 0;
}